The present invention relates to a method of adaptive arithmetic coding, and particularly to that applied for encoding and decoding facsimile image data according to JBIG (Joint Bi-level Image Group) standard, namely the ITU-T recommendation T.85.
Data compression and expansion are usually applied for facsimile image data transmission in order to reduce information amount to be transmitted.
As an international standard of the data compression/expansion, a coding/decoding method called JBIG (facsimile version) is recommended formally as the recommendation T.85 in August 1995, by the ITU-TSS (International Telecommunication Union, Telecommunication Standardization Sector), wherein binary image data are compressed by way of adaptive arithmetic encoding calculating prediction probability of a binary pixel value referring to context defined by neighboring ten pixels.
FIG. 7 is a schematic diagram illustrating principle of the adaptive arithmetic encoding (hereafter abbreviated as the AAE).
In the AAE, a sequence of n binary values (white or black) is represented by a probability interval between maximum value and minimum value of appearance probability of the sequence, n being a positive integer. The probability interval is described by two binary fractions A.sub.n and C.sub.n between 0 to 1, A.sub.n being difference between the maximum value and the minimum value thereof represented by the minimum value C.sub.n.
Referring to FIG. 7, at the beginning of encoding process, that is, when there is given no information of a sequence of pixels to be coded and so the probability interval is 0 to 1, a prediction (white) and its probability (false: .function..sub.1, true: 1-.function..sub.1) for a first pixel P1 is given according to a context. At a first process S.sub.1, where the first pixel P1 is found white, that is, the prediction is true, the probability interval becomes A.sub.1 =1.times.(1-.function..sub.1), which is represented by C.sub.1 =0, and a second prediction (white) and its probability .function..sub.2 is given according to revised context. The second prediction being true, the probability interval becomes A.sub.2 =A.sub.1 .times.(1-.function..sub.2), represented by C.sub.2 =0 at second process. When a prediction is found false at third process S.sub.3, the probability interval becomes A.sub.3 =A.sub.2 .times..function..sub.3, which is represented by C.sub.3 =A.sub.2 .times.(1-.function..sub.3). In the same way, the probability interval becomes A.sub.4 =A.sub.3 .times.(1-.function..sub.4) represented by C.sub.4 =C.sub.3 at process S.sub.4 true, and A.sub.5 =A.sub.4 .times..function..sub.5 represented by C.sub.5 =C.sub.4 +A.sub.4 .times.(1-.function..sub.5) at process S.sub.5 false.
Thus, a binary fraction C.sub.n between 0 to 1, specifying a unique sequence of n pixels, is obtained as encoded value of the sequence of n pixels. The longer the sequence is, the wider column number of the binary fraction C.sub.n becomes. However, the column number can be made narrower than the sequence length n of the pixels by applying appropriate predictions.
For decoding the binary fraction C.sub.n, inverse calculation of the above encoding process is performed. For example, when C.sub.n is smaller than A.sub.1 =1.times.(1-.function..sub.1), the first prediction is known to be true and the first pixel P1 is determined as white at first process. Then, the binary fraction C.sub.n being between the second major interval 0 to A.sub.2 =A.sub.1 .times.(1-.function..sub.2), the second pixel P2 is found also white. At third process, the third pixel P3 is found black, since the binary fraction C.sub.n is larger than C.sub.3 =A.sub.2 .times.(1-.function..sub.3), similar processes following.
In the JBIG standard, the AAE is realized as follows.
The probability interval A.sub.i (i being a positive integer not more than n) is expressed by a hexadecimal less than 0.times.10000 and is controlled always not less than 0.times.8000 by a normalization. That is, when it becomes less than 0.times.8000, it is normalized together with the binary fraction, namely the temporary encoded value C.sub.i, multiplied with 2, being shifted one bit left.
When the normalization is performed eight times, upper eight bits of the temporary encoded value C.sub.i are output as a part of the encoded value C.sub.n of the sequence of n pixels.
In a false process, where a prediction is found false, the probability interval A.sub.i is approximated independent of A.sub.i-1 as: EQU A.sub.i =A.sub.i-1 .times..function..sub.i .apprxeq.A.times..function..sub.i =LSZ.sub.i,
where A represents average probability density of the probability intervals, which are always normalized between 0.times.8000 to 0.times.10000, and the temporary encoded value C.sub.i is calculated as C.sub.i =C.sub.i-1 +A.sub.i -LSZ.sub.i.
On the other hand, the probability interval A.sub.i is calculated as follows in a true process, the temporary encoded value C.sub.i =C.sub.i-1 : EQU A.sub.i =A.sub.i-1 .times.(1-.function..sub.i).apprxeq.A.times.(1-.function..sub.i)=A.sub.i-1 -LSZ.sub.i.
In both processes true and false, the normalization is performed, as above described, when the probability interval A.sub.i becomes less than 0.times.8000. Further, when the prediction, which is pixel value more probable, is found false, the approximation LSZ.sub.i should be smaller than a half, that is less than 0.times.8000. Accordingly, the normalization is performed in every false process.
For dealing with exceptional cases, there are defined several additional rules in the JBIG standard, intricate description thereof, however, omitted here for simplification.
FIG. 6 is a schematic diagrams illustrating an array 61 of the neighboring ten pixels to be referred to, a context 62 defined by the array 61, a learning table 63 where a prediction M1 of one bit (white or black) and a status value M2 at present time are stored for each of possible 2.sup.10 contexts, and a prediction probability table 64, each defined in the JBIG standard for enabling the above approximation.
In the prediction probability table 64, a false approximation M3 giving the approximation LSZ.sub.i of the probability interval A.sub.i to be applied in a false process is prepared for each of 113 status values from 0 to 112, together with a next false status value M4, a next true status value M5 and a switch M6 to be used for adapting the learning table 63 when the normalization is occurred.
Now, usage of the array 61, the context 62, the learning table 63 and the prediction probability table 64 will be described in connection with a conventional AAE coder, referring to FIGS. 2 to 6.
FIG. 2 is a block diagram illustrating a principal configuration of the conventional AAE coder, comprising;
a CPU (Central Processing Unit) 100 for taking charge of arithmetic operation, data processing, control of other parts, and so on. PA1 an image data memory 400 for storing binary image data obtained by scanning a manuscript to be transmitted, PA1 a code data memory 500 for storing received code data, a ROM (Read Only Memory) 200 where the prediction probability table 64 of FIG. 6 and a JBIG program 201 are prepared, PA1 a learning table memory 300 where contents of the learning table 63 are to be written, PA1 a FIFO (First-In-First-Out) memory 600 for buffering encoded code data or decoded image data, and PA1 a bus 700 for connecting each of the above parts. The CPU 100 includes; PA1 a first register 101 for storing a temporary encoded value C, PA1 a second register 102 for storing a binary value of the context 62 of FIG. 6, PA1 a third register 103 for storing a block of data of a line to be coded read out from the image data memory 400, PA1 a fourth register 104 for storing data of corresponding block of a first preceding line of the line to be coded, PA1 a fifth register 105 for storing data of corresponding block of a second preceding line of the line to be coded, PA1 a sixth register 106 for storing a probability interval A and the false approximation M3 read out from the prediction probability table 64, and PA1 a seventh register 107 for storing the prediction M1 and the status value M2 read out from the learning table 63. PA1 the probability interval A is added to the temporary encoded value C, PA1 the probability interval A is revised again to the false approximation M3, PA1 the status value M2 of the learning table 63 corresponding to the concerning context 62 is replaced with the next false status value M4, and PA1 the prediction M1 of the learning table 63 corresponding to the concerning context 62 is inverted when the switch MG is 1. PA1 the probability interval A is reduced from the temporary decoding value C, PA1 the probability interval A is revised once more to the false approximation M3, PA1 the status value M2 of the learning table 63 corresponding to the concerning context 62 is replaced with the next false status value M4, and PA1 the prediction M1 of the learning table 63 corresponding to the concerning context 62 is inverted when the switch M6 is 1. PA1 the step of reading the learning table and the step of reading the prediction probability table in the second pixel processing step are omitted for a bit of the block following a preceding bit whereof the normalization process is not performed by making use of the prediction and the false approximation applied for said preceding bit. PA1 the step of reading the learning table and the step of reading the prediction probability table in the second pixel processing step are omitted for a bit to be decoded of the block following a preceding decoded bit whereof the normalization process is not performed by making use of the prediction and the false approximation applied for said preceding decoded bit.
At beginning of the AAE of binary image data of a manuscript, the prediction M1 and the status value M2 for every of the 2.sup.10 possible contexts in the learning table 63 are initialized to `0`, for example, indicating the prediction `white` and the initial status.
FIG. 3 is a flow chart illustrating operational flow for encoding the binary image data of a line according to the conventional AAE coder of FIG. 2.
At START of the encoding, the probability interval A and the temporary encoded value C are initialized to 0.times.10000 and 0, respectively, and if the concerning line is a first line, the learning table 63 is also initialized as above described.
First, a block of the binary image data of each of concerning line, its preceding line and its next preceding line is read out from the image data memory 400 to be stored into corresponding each of the third, fourth and fifth registers 103, 104 and 105 (at step S41). When there is no preceding line, it is substituted with a sequence of `0` bits.
Then, the context 62 is prepared from the array 61 of neighboring ten pixels (bits), composed of nearest three pixels of the next preceding line, nearest five pixels of the preceding line and preceding two pixels of the concerning line for a concerning pixel (at step S45, steps S42 to S44 being described afterwards), as illustrated in FIG. 6. When the concerning pixel is the beginning of a line, for example, and there is not any corresponding pixel, it is regarded as `0` (white).
Then, pixel processing of the concerning pixel is performed (at step S46) referring to the context.
By repeating steps S45 and S46 by shifting the concerning pixel bit by bit (at step S48), from left to right of the block of the binary image data of the concerning line stored in the third register 103, until end of the block is found (at step S47), coding of the block is performed, and by repeating steps S40, S41, and steps S45 to S48, block by block from left to right until end of the concerning line is found (at step S40), coding of the concerning line is performed.
Now, detailed processes of the pixel processing performed in step S46 are described referring to a flowchart of FIG. 4 and the schematic diagram of FIG. 6.
The context 62 is prepared by ranging the three neighboring bits of the next preceding line, the five neighboring bits of the preceding line and the two neighboring bits of the concerning line in this order as shown in FIG. 6.
Referring to FIG. 4, the prediction Ml and the status value M2 is retrieved first (at step S21) from an entry of the learning table 63 indicated by the context, which is indexed according to 2.sup.10 possible contexts.
Then, the false approximation M3 is read out (at step S22) from the prediction probability table 64 together with the next false status value M4, the next true status value M5 and the switch M6 corresponding to the status value M2, making use of the status value M2 as the index of the prediction probability table 64.
Then (at step S23), the probability interval A is revised to A-M3 (which is revised again to M3 afterwards in false process S25).
Then, it is checked whether the prediction is true or false, that is whether the concerning bit (pixel) coincides with the prediction M1 or not (at step S24).
When the prediction is false, a false process is performed (at step S25), where;
And, a normalization process is performed (at step S27), as the probability interval A=M3 is less than 0.times.8000.
When the prediction is found true at step S24, it is checked whether the probability interval A&lt;0.times.8000 (at step S29). When A.notlessthan.0.times.8000, the pixel processing (step S46 of FIG. 3) of the concerning pixel ends, the temporary encoded value C remaining as it is.
When A&lt;0.times.8000, the normalization process of step S27 is performed after a true process (at step S26), wherein the status value M2 of the learning table 63 corresponding to the concerning context 62 is replaced with the next true status value M5, and the prediction is inverted when the switch M6 is 1.
In the normalization process at step S27, bits of both the probability interval A and the temporary encoded value C are shifted leftwards by one bit and a count number CT is incremented by one, which is repeated until the probability interval A becomes not less than 0.times.8000. When the count number attains to eight during the above repeating, upper eight bits of the temporary encoded value C are output as a part of coded data to the FIFO memory 600, resetting the count number CT to 0.
Thus, the encoding of the binary data according to the AAE is performed pixel by pixel, preparing the context 62, referring to the learning table 63 and the prediction probability table 64 for each pixel.
However, manuscripts to be transmitted by way of facsimile device generally include many white spaces. Therefore, load of the preparation of the context 62 at step S45 is reduced by making use of these white spaces, in the coding method of the conventional AEE coder of FIG. 3. Steps S42 to S44 is provided for the purpose.
After the three blocks of the binary image data are read out at step S41, it is checked (at step S42) whether all pixels of the three blocks are white or not. When they are all white, that is, all `0`, the context 62 remains 0 until end of the concerning block. So, a pixel processing step S43, which is the same with that of step S46, is repeated for each pixel of the block without revising the context 62 until end of the block is found at step S44. Thus, processes at steps S48 and S45 for preparing the context 62 are omitted when data of three blocks are all `0`, reducing operational load.
Decoding of the coded data is performed in a similar way to the operational flow of FIG. 3, and is described referring to FIG. 5.
Before decoding transmitted coded data, the prediction M1 and the status value M2 for every of the 2.sup.10 possible contexts in the learning table 63 are initialized to `0`, in the same way with the coding operation. At START of each line decoding process, the probability interval A is initialized to 0.times.10000, and three bytes, 24 bits, of coded data to be decoded are set in the first register 101 read out from the code data memory 500 and upper two bytes are treated as a temporary decoding value C.
At step S51, the third register 103, where decoded bits will be written, is initialized to 0, and each of corresponding blocks of the binary image data of two preceding lines of the line to be decoded is read out from the image data memory 400 to be stored into corresponding each of the fourth and fifth registers 104 and 105. When there is no preceding line, it is substituted with a sequence of `0` bits.
Then, it is checked whether both the two blocks stored in the registers 104 and 105 are 0 or not (at step S52).
When any bit of the two blocks is not `0`, the context 62 is prepared from the array 61 of neighboring ten pixels (bits), composed of nearest three pixels of the next preceding line, nearest the preceding the preceding line and preceding two decoded pixels of the concerning line for a concerning pixel to be decoded, in a similar way with the encoding of FIG. 3.
Referring to the context, a pixel processing of the concerning pixel is performed (at step S56), and a decoded bit is written in the third register 103 sequentially form left to right.
Steps S55 and S56 are repeated until the block end, that is, the third register is filled with the decoded bits, revising the context 62 by shifting position of the concerning pixel to be decoded, bit by bit (at step S58), and the decoded bits are output to be buffered in the FIFO memory 600.
When the two blocks is found to be 0 at step S52, the pixel processing of the concerning pixel is started (at step S53) with the context 62 being set to 0 and is repeated until a decoded bit is found to be `1`, black, (at step S59), or the block end is found (at step S54). When a decoded bit is found to be `1` at step S59, the process flow goes to step S57 and the decoding of coded data for the block is continued each time revising the context 62 at step S55 by shifting position of the concerning pixel to be decoded, bit by bit, as above described.
Detailed processes of the pixel processing performed at step S56 and S53 are similar to pixel processing performed at steps S46 and S43 described in connection with the flowchart of FIG. 4, and will be described also referring to FIG. 4.
At steps S21 to S23, the prediction M1 and the status value M2 is retrieved from the learning table 63 according to the context 62. Then, the false approximation M3, the next false status value M4, the next true status value M5 and the switch M6 is retrieved according to the status value M2 from the prediction probability table 64. The probability interval A is revised to A-M3 at step S23.
Then, it is checked whether the prediction is true or false, that is whether the concerning bit (pixel) is to be decoded as the same with the prediction M1 or not (at step S24). When A&gt;C, the prediction M1, `0` for example, is determined to be true, and the concerning bit is decided to `0`, while it is decided to be inverse logic of the prediction M1, `1` in the example, when A.rho.C.
When the prediction is false, a false process is performed (at step S25), where;
And, a normalization process is performed (at step S27).
When the prediction is determined to be true at step S24, it is checked whether the probability interval A&lt;0.times.8000 (at step S29). When A.notlessthan.0.times.8000, the pixel processing (step S56 or S53 of FIG. 4) of the concerning pixel ends, the temporary encoded value C remaining as it is.
When A&lt;0.times.8000, the normalization process of step S27 is performed after a true process (at step S26), wherein the status value M2 of the learning table 63 corresponding to the concerning context 62 is replaced with the next true status value M5.
In the normalization process at step S27, bits of both the probability interval A and the temporary decoding value C are shifted leftwards by one bit and a count number CT is incremented by one, which is repeated until the probability interval A becomes not less than 0.times.8000. When the count number attains to eight during the above repeating, one byte, 16 bits, is read out from the code data memory 500 to be replaced with eight lower `0` bits of the first register 101 generated by the shifting up of the temporary decoding value C, resetting the count number CT to 0.
Thus, the decoding of the coded data according to the AAE is performed pixel by pixel.
The learning table 63 is initialized at the beginning of both the encoding and the decoding. It is revised every time when the normalization is performed, but each normalization should occur in both the encoding and the decoding when the same corresponding pixel is processed with the same status value. Therefore, the same binary image data can be decoded. And, the learning table 63 is optimized in the same way along with the encoding and the decoding, by preparing the prediction probability table 64 appropriately.
However, conventional AAE coders had a problem that a certain computational time is needed for processing in real time. In the conventional method described in connection with FIGS. 3 to 5, the contents of the three/two blocks are checked at step S42/S52 for reducing computational load of preparing the context 62 when the context having a value 0 can be applied. However, the learning table 63 and the prediction probability table 64 are retrieved every time when a pixel is encoded or decoded, still needing a considerable load.